package com.klun.tree;

import com.klun.common.Node;

import java.util.HashMap;
import java.util.Stack;

public class MaxTree {

    private Node node;

    public Node get() {
        return node;
    }

    public void set(int[] num){
        Node nodeTem = node;
        int numSize = num.length;

        for (int i = 0; i < numSize; i++) {
            
        }

    }
    public Node compareAndSet(int num , Node oldNode){
        Node newNode;
        int value = oldNode.getValue();

        if(num > value){
            newNode = new Node(num);
            Node rightNode = oldNode.getRight();
            oldNode.setRight(null);
            newNode.setLeft(oldNode);
            newNode.setRight(rightNode);
            return newNode;
        }

        if(num < value){

        }
        return null;
    }

    public static void main(String[] args) {
        int[] arr = {5,6,2,4,9,1,7,8};
        MaxTree maxTree  = new MaxTree();
        Node result = maxTree.getMaxTree(arr);
        int arrLen = arr.length;
        while ((arrLen--)!=0){
            System.out.println(result.value);
        }
    }

    /**
     *  书
     * @param arr
     * @return
     */
    public Node getMaxTree(int[] arr){
        Node[] nArr = new Node[arr.length];

        for (int i = 0; i < arr.length; i++) {
            nArr[i] = new Node(arr[i]);
        }
        Stack<Node> stack = new Stack<>();
        HashMap<Node, Node> lBigMap = new HashMap<>();
        HashMap<Node, Node> rBigMap = new HashMap<>();

        for (int i = 0; i < nArr.length; i++) {
            Node curNode = nArr[i];
            // stack 不为空 ，且新值大于最大值
            while ((!stack.isEmpty()) && stack.peek().value < curNode.value){
                // stack.peek 放入 lMap
                popStackSetMap(stack,lBigMap);
            }
            stack.push(curNode);
        }

        while (!stack.isEmpty()){
            popStackSetMap(stack,lBigMap);
        }

        for (int i = nArr.length-1; i != -1; i--) {
            Node curNode = nArr[i];
            // stack 不为空，且新值大于最大值
            while ((!stack.isEmpty()) && stack.peek().value < curNode.value){
                popStackSetMap(stack,rBigMap);
            }
            stack.push(curNode);
        }

        while (!stack.isEmpty()){
            popStackSetMap(stack,rBigMap);
        }

        Node head = null;
        for (int i = 0; i != nArr.length ; i++) {
            Node curNode = nArr[i];
            Node left = lBigMap.get(curNode);
            Node right = rBigMap.get(curNode);
            // 如果左右都为 0 说明取出了顶值得Node
            if(left == null && right == null){
                head = curNode;
            } else if(left == null){// 左侧为空
                if(right.left == null){
                    right.left = curNode;
                }else {
                    right.right = curNode;
                }
            } else if(right == null){
                if(left.left == null){
                    left.left = curNode;
                }else {
                    left.right = curNode;
                }
            } else{
                Node parent = left.value < right.value? left:right;
                if(parent.left  == null){
                    parent.left = curNode;
                } else {
                    parent.right = curNode;
                }
            }
        }
        return head;
    }

    /**
     *
     * @param stack
     * @param map
     */
    public void popStackSetMap(Stack<Node> stack, HashMap<Node, Node> map){
        // 取出一个值
        Node popNode = stack.pop();
        if(stack.isEmpty()){
            map.put(popNode,null);
        } else {
            // 取出顶值 作为下一个值得key
            map.put(popNode,stack.peek());
        }
    }

}
